package club.babyf.nativeai.demo.algorithm;

/**
 * _27_Trap.
 *
 * @author zhanglei.
 * @date 2025/8/8 20:41.
 * @description 接雨水.
 */
public class _27_Trap {

    public int trap(int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }

        int left = 0;
        int right = heights.length - 1;
        int leftMax = 0;
        int rightMax = 0;
        int water = 0;

        while (left < right) {
            if (heights[left] < heights[right]) {
                if (heights[left] >= leftMax) {
                    leftMax = heights[left];
                } else {
                    water += leftMax - heights[left];
                }
                left++;
            } else {
                if (heights[right] >= rightMax) {
                    rightMax = heights[right];
                } else {
                    water += rightMax - heights[right];
                }
                right--;
            }
        }

        return water;
    }

    public static void main(String[] args) {
        _27_Trap trap = new _27_Trap();

        int[] heights = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        System.out.println(trap.trap(heights));

        int[] heights2 = {4, 2, 0, 3, 2, 5};
        System.out.println(trap.trap(heights2));
    }

}
